一个「开心字符串」定义为：

仅包含小写字母 ['a', 'b', 'c'].
对所有在 1 到 s.length - 1 之间的 i ，满足 s[i] != s[i + 1] （字符串的下标从 1 开始）。

比方说，字符串 **” abc”**， “ ac”，”b” 和 “ abcbabcbcb” 都是开心字符串，但是 **” aa”**，
“ baa” 和 “ ababbc” 都不是开心字符串。

给你两个整数 n 和 k ，你需要将长度为 n 的所有开心字符串按字典序排序。

请你返回排序后的第 k 个开心字符串，如果长度为 n 的开心字符串少于 k 个，那么请你返回 空字符串 。

示例 1：

**输入：** n = 1, k = 3
**输出：** "c"
**解释：** 列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。

示例 2：

**输入：** n = 1, k = 4
**输出：** ""
**解释：** 长度为 1 的开心字符串只有 3 个。

示例 3：

**输入：** n = 3, k = 9
**输出：** "cab"
**解释：** 长度为 3 的开心字符串总共有 12 个 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] 。第 9 个字符串为 "cab"

示例 4：

**输入：** n = 2, k = 7
**输出：** ""

示例 5：

**输入：** n = 10, k = 100
**输出：** "abacbabacb"

提示：

1 <= n <= 10
1 <= k <= 100

Problem: 1415. 长度为 n 的开心字符串中字典序第 k 小的字符串

[TOC]

思路

先从暴力入手，再来优化

解题方法

步骤一： 首先我们可以看出第一个字母是三种可能a、b、c这三种可能，然后第二个字母分析如下：

如果第一个字母是a，则，第二个字母有两种可能b、c；
如果第一个字母是b，则，第二个字母有两种可能a、c；
如果第一个字母是c，则，第二个字母有两种可能a、b；

步骤二： 依此类推，第三个字母对应的第二个字母都有两种情况，因此，如果长度为n的字符串，那么总的数量可能为3\times 2^{n-1种可能。所以可以根据这个式子来判断k是否超过了：

如果k>3\times 2^{n-1，则返回空字符串；
如果k\leq 3\times 2^{n-1，则说明存在；

步骤三： 接着可以分析出来字符串中第一个字母分别是a、b、c的数量其实是相等的，即2^{n-1种，因此我们可以根据k来判断返回的字符串res的第一个字符是a还是b还是c：

如果(k-1)/ 2^{n-1}==0，则说明第一个字符是a；
如果(k-1)/ 2^{n-1}==1，则说明第一个字符是b；
如果(k-1)/ 2^{n-1}==2，则说明第一个字符是c；

步骤四： 然后在确定第一个字符之后，k变为了k=(k-1)mod 2^{n-1，我们可以知道以后的每个字符都是有且只有两种情况，因为不能和上一个字符相同，所以每个分支的总可能性为2^{n-2种可能。我们需要通过k来判断是属于前一个分支还是后一个分支。例如假设前一个字符为b，则下一个字符只有a、c两种可能，而a一定是排在c的前面，所以：

如果k/ 2^{n-2}==0，则说明下一个字符是a；
如果k/ 2^{n-2}==1，则说明下一个字符是c；

步骤五： 最后一直重复步骤四，直到分支的可能性为1，即s^{n-i}==1，就是所有的字符串全部算出来了。

复杂度

时间复杂度:

O(log(n))
空间复杂度:

O(1)

Code

[]
class Solution
{
public:
    string getHappyString(int n, int k)
    {
        int sum = 3 * pow(2, n - 1);
        string res;
        if (sum < k)
            return res;
        k = k - 1;
        sum = sum / 3;
        if (k / sum == 0)
            res += 'a';
        else if (k / sum == 1)
            res += 'b';
        else
            res += 'c';
        k = k % sum;
        n--;
        char s = res[res.size() - 1];
        while (n > 0)
        {
            sum = sum / 2;
            s = res[res.size() - 1];
            if (k / sum == 0)
            {
                if (s == 'a')
                    res += 'b';
                else
                    res += 'a';
            }
            else
            {
                if (s == 'c')
                    res += 'b';
                else
                    res += 'c';
            }
            k = k % sum;
            n--;
        }
        return res;
    }
};

1415-长度为 n 的开心字符串中字典序第 k 小的字符串

思路

解题方法

复杂度

Code